package crawler.web.other;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;

import crawler.web.deduplicate.BitUtil;
import crawler.web.deduplicate.CombinationGenerator;

public class SimHashSet {
	ArrayList<Long> simHashs = new ArrayList<Long>();

	static Comparator<Long> comp = new Comparator<Long>() {
		public int compare(Long o1, Long o2) {
			if (o1.equals(o2))
				return 0;
			return (isLessThanUnsigned(o1, o2)) ? -1 : 1;
		}
	}; // Comparator comp

	public static boolean isLessThanUnsigned(long n1, long n2) {
		return (n1 < n2) ^ ((n1 < 0) != (n2 < 0));
	}

	public void sort() {
		Collections.sort(simHashs, comp);
	}

	public boolean contains(long key) {
		int low = 0;
		int high = simHashs.size() - 1;

		while (low <= high) {
			int mid = (low + high) >>> 1;
			Long midVal = simHashs.get(mid);
			int cmp = comp.compare(midVal, key);

			if (cmp < 0)
				low = mid + 1;
			else if (cmp > 0)
				high = mid - 1;
			else
				return true; // key found
		}
		return false; // key not found
	}

	public boolean containSim(long fingerPrint, int k) {
		//首先二分法查找
		if (contains(fingerPrint)) {
			return true;
		}
		//System.out.println("o:"+Long.toBinaryString(fingerPrint));

		//然后逐次探查法
		//查找差1位直到差k位
		for (int ki = 1; ki <= k; ++ki) {
			//System.out.println("ki:"+ki);
			CombinationGenerator x = new CombinationGenerator(64, ki);
			//int count =0;
			while (x.hasMore()) {
				int[] indices = x.getNext();
				long simFP = fingerPrint;
				for (int i = 0; i < indices.length; i++) {
					simFP = simFP ^ 1L << indices[i];
				}
				//System.out.println(Long.toBinaryString(simFP));
				if (contains(simFP)) {
					return true;
				}
				//++count;
			}
			//System.out.println("count:"+count);
		}

		return false;
	}

	public List<Long> getSim(long fingerPrint, int k) {
		List<Long> retAll = new LinkedList<Long>();
		for (int ki = 1; ki <= k; ++ki) {
			CombinationGenerator x = new CombinationGenerator(64, ki);
			while (x.hasMore()) {
				int[] indices = x.getNext();
				long simFP = fingerPrint;
				for (int i = 0; i < indices.length; i++) {
					simFP = simFP ^ 1L << indices[i];
				}
				retAll.add(simFP);
			}
		}
		return retAll;
	}

	public void addSimHash(String key) {
		//long t = Long.parseLong(key,2);
		long t = BitUtil.decodeLong(key);
		//System.out.println(t);
		simHashs.add(t);
	}

}
